// https://leetcode.cn/problems/min-cost-climbing-stairs/
// Created by ade on 2022/8/16.
// 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
//
//你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
//
//请你计算并返回达到楼梯顶部的最低花费。
// {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
// 第0级台阶： minCost[0] = min(cost[-1], cost[0]) = min(0, cost[0]) = 0，
//
// 第1级台阶： minCost[1] = min(cost[0], cost[1])。

// 第2级台阶： minCost[2] = minCost[0] + cost[2] , cost[1]。

// 第3级台阶： minCost[2] = minCost[2] + cost[2] , cost[1] + cost[3]。
//
#include <iostream>
#include <vector>


using namespace std;

class Solution {
public:
    int minCostClimbingStairs(vector<int> &cost) {
        int len = cost.size();
        int dp[len];
        dp[0] = 0;
        dp[1] = min(cost[0], cost[1]);
        for (int i = 2; i < len; i++) {
            dp[i] = min(dp[i - 1] + cost[i], dp[i - 2] + cost[i - 1]);// 前1步和前2步的最小值
        }
        return dp[len - 1];
    }
};

int main() {
    Solution so;
    vector<int> nums = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
    //  0 - 0                0
    //  1 - 1, 100           1
    //  2 - 1 + 1, 0 + 100   2
    //  3 - 2 + 1, 1 + 1     2
    //  4 - 2 + 1, 2 + 1     3
    //  5 - 3
    cout << so.minCostClimbingStairs(nums) << endl;
    return 0;
}